package com.example.question.dp.dp2;

/**
 * @Date 2023-07-23
 * @Author Jonathan
 * @description 多重背包问题
 */
public class Code07_Knapsack {

    public static void main(String[] args) {
        int[] w = new int[]{3, 4, 5};
        int[] v = new int[]{10, 15, 12};
        int capacity = 11;
        int f0 = f0(w, v, capacity, 0);
        System.out.println("f0 = " + f0);
        int f1 = f1(w, v, capacity, -1);
        System.out.println("f1 = " + f1);
        int f2 = f2(w, v, capacity, 0);
        System.out.println("f2 = " + f2);
        int f3 = f3(w, v, capacity, -1);
        System.out.println("f3 = " + f3);
    }

    /**
     * 多重背包问题（每个物体的数量无限）
     */
    private static int f0(int[] weights, int[] values, int capacity, int index) {
        if (index == weights.length) {
            return 0;
        }
        int max = 0;
        for (int i = index; i < weights.length; i++) {
            // 装不下的剪枝掉了
            if (capacity < weights[i]) {
                continue;
            }

            int val = f0(weights, values, capacity - weights[i], i);
            int val1 = val + values[i];
            max = Math.max(val1, max);
        }
        return max;
    }

    private static int f1(int[] weights, int[] values, int capacity, int index) {
        int max = 0;
        for (int i = index; i < weights.length; i++) {
            int childIndex = i + 1;
            // 层数剪枝
            if (childIndex >= weights.length) {
                continue;
            }
            // 装不下的剪枝掉
            if (capacity < weights[childIndex]) {
                continue;
            }

            int val = f1(weights, values, capacity - weights[childIndex], childIndex);
            max = Math.max(val, max);
        }
        // 相当于是多叉树的后续遍历 先汇总所有孩子节点的情况之后 再根据情况判断当前节点是不是需要加上
        // 相当于是返回的是下一层的   当前层的要不要加上 还需要根据index进行判断
        return max + (index == -1 ? 0 : values[index]);
    }

    /**
     * 0-1背包问题（也就是每个物体要和不要的问题）
     */
    private static int f2(int[] weights, int[] values, int capacity, int index) {
        // 边界条件
        if (index >= weights.length) {
            return 0;
        }
        int max = 0;
        // 可以理解成是weights.length棵多叉树  取每一个棵多叉树的最大值
        for (int i = index; i < weights.length; i++) {
            // 剪枝之后 就过滤掉装不下的
            if (capacity < weights[i]) {
                continue;
            }
            // 每个物体只有一个，用index进行剪枝
            int val = f2(weights, values, capacity - weights[i], i + 1) + values[i];
            max = Math.max(val, max);
        }
        return max;
    }

    private static int f3(int[] weights, int[] values, int capacity, int index) {
        // 边界条件
        int max = 0;
        for (int i = index; i < weights.length; i++) {
            int childIndex = i + 1;
            // 这样就没有下一层了 剪枝掉
            if (childIndex >= weights.length) {
                continue;
            }
            // 剪枝之后 就过滤掉装不下的了
            if (capacity < weights[childIndex]) {
                continue;
            }
            int val = f3(weights, values, capacity - weights[childIndex], childIndex);
            max = Math.max(val, max);
        }
        return (index == -1 ? 0 : values[index]) + max;
    }
}
